#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_map>
using namespace std;

//435.无重叠区间
int eraseOverlapIntervals(vector<vector<int>>& intervals){
    //删除最少的区间，相当于保留最多的区间
    //先将所有区间按照左端点排序
    sort(intervals.begin(), intervals.end());

    int n = intervals.size();
    //左指针表示上一个区间的左端点，右指针表示上一个区间的右端点
    int left = intervals[0][0], right = intervals[0][1];
    int ret = 0;
    for (int i = 1; i < n; i++){
        int a = intervals[i][0], b = intervals[i][2];

        //如果当前区间的左端点的值小于上一个区间的右端点的值，更新右指针为两个区间右端点最小的
        //贪心策略，上一个区间越小，和当前区间的重叠率就越小
        if(a<right){
            left = 1;
            right = min(right, b);
            ret++;
        }
        //如果大于等于，直接更新左右指针
        else{
            left = a, right = b;
        }
    }

    return ret;
}

//452.用最少量的箭引爆最多的气球
int findMinArrowShots(vector<vector<int>>& points){
    //区间问题，找到公共区间合并
    //先将所有区间按照左端点排序，重叠的区间是连续的（相当于交集）
    sort(points.begin(), points.end());

    int n = points.size();
    int ret = 0;
    //左右指针表示上个区间的左右端点
    int left = points[0][0], right = points[0][1];

    for (int i = 1; i < n; i++){
        int a = points[i][0], b = points[i][1];

        //如果当前区间的左端点小于等于上个区间的右端点，取公共区间，右端点取两个中最小的
        //这里等于也算是重叠
        if(a<=right){
            left = a;
            right = min(right, b);
        }
        //如果大于，说明没有公共区间，个数加1，更新左右指针
        else{
            ret++;
            left = a, right = b;
        }
    }

    return ret + 1;
}

//1162.可被3整除的最大和
int maxSumDivThree(vector<int>& nums){
    //正难则反思想
    //求出所有和
    int sum=0;
    //可以直接sort排序后查找，但是时间复杂度为n方
    //这里用分类讨论直接遍历一遍，时间复杂度为n
    //x1,x2表示模上3等于1，y1,y2表示模上3等于2
    int x1, x2, y1, y2;
    x1 = x2 = y1 = y2 = INT_MAX;
    for(auto num : nums){
        sum += num;
        if (num % 3 == 1&&num<=x1){
            x2=x1;
            x1 = num;
        }
        else if(num%3==1&&x1<=num&&num<=x2){
            x2 = num;
        }
        if (num % 3 == 2 && num <= y1){
            y2=y1;
            y1 = num;
        }
        else if (num % 3 == 2 && y1 <= num && num <= y2){
            y2 = num;
        }
    }

    //如果数组和模上3等于1，找到其中最小的x1,最小的y1和次小的y2
    if(sum%3==1){
        if(y1!=INT_MAX&&y2!=INT_MAX){
            return (sum - x1) > (sum - y1 - y2) ? sum - x1 : sum - y1 - y2;
        }
        else{
            return sum - x1;
        }
    }
    //如果数组和模上3等于2，找到其中最小的x1和次小的x2，最小的y1
    else if(sum%3==2){
        if(x1!=INT_MAX&&x2!=INT_MAX){
            return (sum - x1 - x2) > (sum - y1) ? sum - x1 - x2 : sum - y1;
        }
        else{
            return sum - y1;
        }
    }

    //如果模上3等于0，直接返回
    return sum;
}

//1054.距离相等的条形码
vector<int> rearrangeBarcodes(vector<int>& barcodes){
    int n = barcodes.size();
    //创建一个哈希表用来统计数字的个数
    unordered_map<int, int> hash;
    //一个用来标记个数最多的数字，一个用来记录最多数字的个数
    int maxval = 0, maxcount = 0;
    for(auto x : barcodes){
        if(++hash[x]>maxcount){
            maxcount=hash[x];
            maxval = x;
        }
    }

    //间隔排列，先排列偶数位并且是最多的那个数字，其余数字随便排列
    vector<int> ret(n);
    int index = 0;
    while(maxcount--){
        ret[index] = maxval;
        index += 2;
    }

    //从哈希表中删除最多的那个数
    hash.erase(maxval);
    //将剩下的数依次填充剩余位，偶数位没有填完，优先偶数位，然后奇数位
    for(auto& [num,count] : hash){
        while(count--){
            if(index>=n){
                index = 1;
            }
            ret[index]=num;
            index += 2;
        }
    }

    return ret;
}

//767.重构字符串
string reorganizeString(string s){
    //和上一道题思路一样
    unordered_map<char,int> hash;
    char maxval = 'a';
    int maxcount = 0;
    for(auto ch : s){
        if(++hash[ch]>maxcount){
            maxcount=hash[ch];
            maxval = ch;
        }
    }

    int n=s.size();
    //如果最多的个数超过一半，直接结束,鸽巢原理
    if(maxcount>(n+1)/2){
        return "";
    }

    string ret;
    ret.resize(n);
    int index=0;
    while(maxcount--){
        ret[index] = maxval;
        index += 2;
    }

    hash.erase(maxval);
    for(auto& [ch,count] : hash){
        while(count--){
            if(index>=n){
                index = 1;
            }
            ret[index] = ch;
            index += 2;
        }
    }

    return ret;
}

int main(){

    return 0;
}